#!/bin/python
# -*- coding:utf-8 -*-


def sort_select(a, sort_method='ASC'):
    """
    选择排序
    """
    for i in range(len(a) - 1):
        max_index = i
        for j in range(i + 1, len(a)):
            if sort_method == 'ASC':
                if a[j] < a[max_index]:
                    max_index = j
            else:
                if a[j] > a[max_index]:
                    max_index = j

        tmp = a[i]
        a[i] = a[max_index]
        a[max_index] = tmp
    return a


print(sort_select([3, 4, 9, 2, 1, 10, 9, 6], 'ASC'))


def sort_bubble(a, sort_method='ASC'):
    """
    冒泡排序
    :param a:
    :param sort_method:
    :return:
    """
    for i in range(len(a) - 1):
        for j in range(i + 1, len(a)):
            if sort_method == 'ASC':
                if a[i] > a[j]:
                    tmp = a[i]
                    a[i] = a[j]
                    a[j] = tmp
            else:
                if a[i] < a[j]:
                    tmp = a[i]
                    a[i] = a[j]
                    a[j] = tmp
    return a


print(sort_bubble([3, 4, 9, 2, 1, 10, 9, 6], 'DESC'))


def sort_insert(a, sort_method='ASC'):
    """插入排序"""
    for i in range(len(a)):
        if sort_method == 'ASC':
            while i > 0 and a[i] < a[i - 1]:
                tmp = a[i]
                a[i] = a[i - 1]
                a[i - 1] = tmp
                i = i - 1
        else:
            while i > 0 and a[i] > a[i - 1]:
                tmp = a[i]
                a[i] = a[i - 1]
                a[i - 1] = tmp
                i = i - 1
    return a


print(sort_insert([3, 4, 9, 2, 1, 10, 9, 6], 'ASC'))


def sort_quick(a, start, end):
    """
    快排的思想：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

    百度百科给的算法：

    一趟快速排序的算法是：
    1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
    2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
    3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
    4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
    5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。
    找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
    """
    if start < end:
        i, j = start, end
        base = a[i]
        while i < j:
            # 后半部分逐一和基数对比
            while i < j and base <= a[j]:
                j = j - 1
            a[i] = a[j]

            # 前半部分逐一和基数对比
            while i < j and base >= a[i]:
                i = i + 1
            a[j] = a[i]

        a[i] = base
        sort_quick(a, start, i - 1)
        sort_quick(a, j + 1, end)

    return a


print(sort_quick([3, 4, 9, 2, 1, 10, 9, 6], 0, 7))
